import time
import random
from alg import insertion_sort, bubble_sort, quick_sort, heap_sort
from generator import (
    generate_test_data,
    generate_sorted_data,
    generate_reverse_sorted_data,
    generate_partially_sorted_data
)

def run_test(sort_func, test_data, data_desc):
    """运行单个测试并返回结果"""
    data_copy = test_data.copy()
    start_time = time.time()
    sorted_result = sort_func(data_copy)
    end_time = time.time()
    is_correct = sorted_result == sorted(test_data)
    return {
        'algorithm': sort_func.__name__,
        'data_desc': data_desc,
        'is_correct': is_correct,
        'time': end_time - start_time,
        'input_size': len(test_data)
    }

def run_all_tests(test_sizes):
    """运行所有测试并打印结果"""
    sort_functions = [insertion_sort, bubble_sort, quick_sort, heap_sort]
    data_generators = [
        ('Random Data', generate_test_data),
        ('Sorted Data', generate_sorted_data),
        ('Reverse Sorted Data', generate_reverse_sorted_data),
        ('Partially Sorted Data', generate_partially_sorted_data)
    ]
    
    results = []
    for size in test_sizes:
        for data_desc, generator in data_generators:
            test_data = generator(size)
            for func in sort_functions:
                result = run_test(func, test_data, data_desc)
                results.append(result)
    
    # 打印结果表格
    print("{:<20} {:<25} {:<15} {:<15} {:<10}".format(
        "Algorithm", "Data Description", "Input Size", "Time (s)", "Correct"))
    print("-" * 85)
    for result in results:
        print("{:<20} {:<25} {:<15} {:<15.6f} {:<10}".format(
            result['algorithm'],
            result['data_desc'],
            result['input_size'],
            result['time'],
            "Yes" if result['is_correct'] else "No"
        ))
    
    # 分析并打印每个算法的性能排名
    analyze_performance(results)

def analyze_performance(results):
    """分析并打印每个算法的性能排名"""
    print("\nPerformance Analysis:")
    data_types = set(result['data_desc'] for result in results)
    for data_type in data_types:
        print(f"\n{data_type}:")
        for size in sorted(set(result['input_size'] for result in results)):
            size_results = [
                r for r in results 
                if r['data_desc'] == data_type and r['input_size'] == size
            ]
            if not size_results:
                continue
            # 按时间排序（升序）
            sorted_results = sorted(size_results, key=lambda x: x['time'])
            print(f"  Input Size: {size}")
            for rank, result in enumerate(sorted_results, 1):
                print(f"    {rank}. {result['algorithm']}: {result['time']:.6f}s")

if __name__ == "__main__":
    test_sizes = [100, 500, 1000]  # 可调整测试数据大小
    run_all_tests(test_sizes)  